This invention is in the field of fast packet switched data communication, and is more specifically directed to the prototyping of switch architectures and traffic management algorithms.
In the field of digital communications, whether applied to voice, video, or data communication, various communication techniques have been developed for routing messages among nodes, or processors, that are connected over a network. One technique is referred to as datagram forwarding, where the sending unit transmits the entirety of a variable length packet, along with header information indicating the origin and destination addresses in the network, to a collection center for temporary storage and forwarding to the message destination. Another technique utilizes synchronous time-division multiplexers or circuit switches, which are computers or processors that receive, from multiple sources, fixed length frames that each consist of a certain number of fixed length packets. According to this technique, the synchronous time-division multiplexer or circuit switch then composes outgoing frames from the packets of the incoming frames and, without temporarily storing the packets, transmits these outgoing frames over outgoing lines, for example in time-division multiplexed fashion.
Within the confines of a workgroup or local area network (LAN), datagram forwarding is performed using repeaters and, more recently, packet switches. According to the packet switching approach, certain network nodes operate as concentrators to receive portions of messages, referred to as packets, from the sending units. These packets may be stored at the concentrator, and are then routed to a destination concentrator to which the receiving unit indicated by the packet address is coupled. The size of the packet refers to the maximum upper limit of information which can be communicated between concentrators (i.e., between the store and forward nodes), and is typically a portion of a message or file. Each packet includes header information relating to the source network address and destination network address, which permits proper routing of the message packet. Packet switching ensures that routing paths are not unduly dominated by long individual messages, and thus reduces transmission delay in the store-and-forward nodes. Fast packet switching refers to packet switching techniques that operate at high data rates, up to and exceeding hundreds of megabits per second.
A well-known example of a fast packet switching protocol, which combines the efficiency of packet switching with the predictability of circuit switching, is asynchronous transfer mode (generally referred to as "ATM"), in which packet lengths and organization are fixed, regardless of message length or data type (i.e., voice, data, or video). The fixed packets according to the ATM protocol are referred to as "cells", and each ATM cell is composed of a fifty-three bytes, five of which are dedicated to the header and the remaining forty-eight of which serve as the payload. According to this protocol, larger packets are made up of a number of fixed-length ATM cells.
The architecture of conventional fast packet switches may be considered, at a high level, as a number of inter-communicating processing blocks. FIG. 1 illustrates the high-level common architecture of a conventional fast packet switch. In this switch, ports P.sub.0 through P.sub.n are in communication with various nodes, which may be computers or other switches. Each of ports P.sub.0 through P.sub.n receive data over an incoming link, and transmits data over an outgoing link. Each of ports P.sub.0 through P.sub.n are coupled to switch fabric F, which effects the routing of a message from the one of ports P.sub.0 through P.sub.n associated with the upstream node on the path to the source of packet, to the one of ports P.sub.0 through P.sub.n associated with the downstream node on the path to the destination of the packet. In this fast packet switching architecture, individual packets are routed from one of ports P.sub.0 through P.sub.n to switch fabric F to another one of P.sub.0 through P.sub.n ; each of ports P.sub.0 through P.sub.n have sufficient capability to divide the packet into slices (when on the input end) and to reconstruct slices into a packet (when on the output end). Arbiter A is provided to control the queuing of packets into and out of switch fabric F, and to control the routing operation of switch fabric F accordingly.
While the high-level architecture of fast packet switches may be substantially common, different architectural approaches are used in the implementation of the fast packet switch. These approaches determine the location (input, output, or both) and depth of cell queues or buffers, and also the type of routing used within switch fabric. For example, one architecture may operate by ports P.sub.0 through P.sub.n forwarding each received cell immediately to switch fabric F, which transfers cells at its input interfaces to its output interfaces in a time-division multiplexed fashion; on the output side, each cell that is output from switch fabric F is appended to a FIFO queue at its addressed one of ports P.sub.0 through P.sub.n. Another architecture may utilize input queues at ports P.sub.0 through P.sub.n, with arbiter A controlling the order in which cells are applied from the input queues to switch fabric F, which operates in a crossbar mode. Another architecture may utilize both input and output queues at ports P.sub.0 through P.sub.n, with switch fabric F and arbiter A operating as a multistage interconnection network. These and other various architectures are known in the field of fast packet switching.
Also as is well known in the art, actual communication traffic is neither uniform nor independent; instead, real traffic is relatively bursty, particularly in the communication of data and compressed video. As such, traffic management algorithms are often utilized in fast packet switching to manage the operation of the switch and to optimize switch performance. Examples of well-known traffic management algorithms include traffic shaping, flow control, and scheduling. A survey of conventional traffic management algorithms is described in Gilbert, et al., "Developing a cohesive traffic management strategy for ATM Networks", IEEE Communications Magazine (October 1991), pp. 36-45. It has been observed that the performance of a packet switch is often determined as much by the effectiveness of its traffic management algorithms as by the actual speed of the packet forwarding datapath. Because of the significant effect of traffic management algorithms on switch performance, significant development has been and is being undertaken in improvement of traffic management techniques in fast packet switches.
It has been observed, in connection with the present invention, that the testing and evaluation of experimental fast packet switch architectures and experimental traffic management algorithms is very difficult. The non-uniformity and dependence of real switch traffic (as noted above) renders modeling of fast packet switch operation to be very difficult and inaccurate, especially in bursty applications such as data and compressed video communication. In the evaluation of traffic management algorithms, this difficulty is exacerbated by the wide array of architectures in which fast packet switching is implemented, particularly when such architectures are implemented by way of application-specific integrated circuits (ASICs) in which case the prototypes are both expensive and time-intensive to fabricate and operate. In addition, conventional fast packet switching simulations are extremely slow, with rates often below 10 cells/second, resulting in extremely long simulation runs and also the inability to detect high-speed errors.
By way of further background, Stiliadis, et al., "FAST: An FPGA-Based Simulation Testbed for ATM Networks", 1996 IEEE International Conference on Communications: Conference Record, Vol. 1 (IEEE, 1996), pp. 374-378, describes the construction of hardware simulation of ATM switches using high-density field programmable gate arrays (FPGAs). According to this approach, however, the simulation does not achieve full-speed (or "real-speed") port operation, and as such can only simulate actual fast packet switch operation.
By way of still further background, multiple-slice organization of switch fabric in fast packet switching is known, as described in Suzuki, et al. "Output Buffer Switch Architecture for ATM", Proceedings of International Conference on Communications (ICC, 89) (IEEE, 1989), pp. 99-103. As described therein, multiple-slice switch fabric is useful in the reducing the I/O burden on the switch fabrics.